package com.kingwood.algorithm.zuochengyun.digui;

/**
 * @Author 22025812
 * @Description: 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
 * 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
 * 如果不存在每个袋子都装满的方案返回-1
 * @Date: 2024/3/11 18:03
 * @Modified By：
 * @Version 1.0
 */
public class AppleMinBags {

    public static int minBags(int apples) {
        int ans = f(apples);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    // 当前还有rest个苹果，使用的每个袋子必须装满，返回至少几个袋子
    public static int f(int rest) {
        if (rest < 0) {
            return Integer.MAX_VALUE;
        }

        if (rest == 0) {
            return 0;
        }

        int p1 = f(rest - 8);
        int p2 = f(rest - 6);

        p1 += p1 != Integer.MAX_VALUE ? 1 : 0;
        p2 += p2 != Integer.MAX_VALUE ? 1 : 0;

        return Math.min(p1, p2);
    }

    public static void main(String[] args) {
        for (int apple = 0; apple < 100; apple++) {
            System.out.println(apple + " : " + minBags(apple));
        }
    }
}
